package leetcode.D300.T253;

import java.util.Arrays;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-02-24 18:28:47 星期四
 */
class Solution {
    /**
     * 这道题可以转换为，在同一个时刻最多有多少会议在进行中
     * 立马联想到差分数组，因为差分数组可以迅速对某个区间进行增减操作。对于每个会议，只要在对应的区间上加1
     * 然后根据差分数组，还原回数量数组，再遍历得到最大值
     *
     * 不过这种做法，需要开辟一个大小为T的数组，但是这题中T可能到10^4，很大，所以差分数组的效率不高
     *
     * 因此转化思路，模拟差分数组的遍历过程，先将所有会议的开始和结束时刻放到一个时间线上（timeLine记录）
     * 然后根据时间顺序从小到大排序（这里我用负数代表该时刻是某个会议的结束时间），排序的方式很巧妙：
     * 由于有正数有负数，所以首要的是根据绝对值排序，如果相等，那么结束时刻要排在开始时刻之前（必须！）
     * 最后一趟遍历这个数组，遇到正数，count++，遇到负数，count--，用result记录count的最大值，作为最终结果
     *
     * 第二种算是差分数组的变体形式，模拟了差分数组的遍历过程，复杂度更低，为O(2*n)=O(n)，n为会议数量
     */
    public int minMeetingRooms(int[][] intervals) {
        int n = intervals.length;
        Integer[] timeLine = new Integer[n * 2];
        for(int i=0; i<n; ++i) {
            timeLine[i*2] = intervals[i][0];
            timeLine[i*2+1] = -intervals[i][1];
        }
        Arrays.sort(timeLine, (a, b) -> {
            if (Math.abs(a) != Math.abs(b))
                return Math.abs(a) - Math.abs(b);
            return a-b;
        });
        int result = 0, count = 0;
        for(int i=0; i<2*n; ++i) {
            if (timeLine[i] >= 0)
                count++;
            else
                count--;
            result = Math.max(count, result);
        }
        return result;
    }
}